package sort.comparison;

/**
 * Created by Yasin H on 2017/8/1.
 */
public class Shell extends Base {

    //shortArrays 2
    //middleArrays 55
    //middleArraysR 62
    //longArrays 3400
    //longArraysR 4400

    public static void sort(Comparable[] a) {
        int N = a.length;
        int h = 1;
        while (h < N / 3)
            h = 3 * h;
        while (h >= 1) {
            for (int i = h; i < N; i++) {
                for (int j = i; j >= h && less(a[j], a[j - h]); j -= h) {
                    swap(a, j, j - h);
                }
            }
            h = h / 3;
        }
    }

}
